/* BFS广度优先遍历 之 队列实现 */
function fn1() {
    const tree = {
        name: "a",
        children: [
            {
                name: "b",
                children: [
                    { name: "d" },
                    {
                        name: "e",
                        children: [
                            { name: "g" }
                        ]
                    },
                ]
            },
            {
                name: "c",
                children: [
                    {
                        name: "f", children: [
                            { name: "h" }
                        ]
                    },
                ]
            }
        ]
    }

    const q = [tree]

    while (q.length) {
        const item = q.shift()
        console.log(item.name);

        // 将当前元素的孩子添加到队尾
        item.children && item.children.forEach(
            c => q.push(c)
        )
    }

    console.log("BFS广度优先遍历结束");
}

/* DFS深度优先遍历 之 递归实现 */
function fn2() {
    const tree = {
        name: "a",
        children: [
            {
                name: "b",
                children: [
                    { name: "d" },
                    {
                        name: "e",
                        children: [
                            { name: "g" }
                        ]
                    },
                ]
            },
            {
                name: "c",
                children: [
                    {
                        name: "f", children: [
                            { name: "h" }
                        ]
                    },
                ]
            }
        ]
    }

    function dfs(value) {
        console.log(value.name);
        value.children && value.children.forEach(
            c => dfs(c)
        )
    }

    dfs(tree)

    console.log("DFS 深度优先遍历结束");
}

/* DFS深度优先遍历 之 栈实现 */
function fn3() {
    const tree = {
        name: "a",
        children: [
            {
                name: "b",
                children: [
                    { name: "d" },
                    {
                        name: "e",
                        children: [
                            { name: "g" }
                        ]
                    },
                ]
            },
            {
                name: "c",
                children: [
                    {
                        name: "f", children: [
                            { name: "h" }
                        ]
                    },
                ]
            }
        ]
    }

    // 后入先出是为栈
    const stack = [tree]

    while(stack.length){
        const item = stack.pop()
        console.log(item.name);

        if(item.children){
            for(let i = item.children.length-1;i>-1;i--){
                const c = item.children[i]
                stack.push(c)
            }
        }
    }

    console.log("DFS 深度优先遍历结束");
}

fn3()